/*
687. 最长同值路径
https://leetcode.cn/problems/longest-univalue-path/description/
中等 2024/11/15
*/

class Solution {
public:
    int ans = 0;
    int dfs(TreeNode* root, int val) {//至下而上
        if (!root) return 0;
        int l = dfs(root->left, root->val);
        int r = dfs(root->right, root->val);
        ans = max(ans, l+r);//判断当前节点的左右孩子符合条件的有几个
        return root->val == val ? max(l, r) + 1 : 0;//判断当前节点跟其父节点是否相同,相同则判断走左边还是走右边值更大
    }
    int longestUnivaluePath(TreeNode* root) {
        if (!root) return 0;
        dfs(root, root->val);
        return ans;
    }
};